/**
 * Suppose an array of length n sorted in ascending order is rotated between 1 and
 * n times. For example, the array nums = [0,1,4,4,5,6,7] might become:
 * <p>
 * <p>
 * [4,5,6,7,0,1,4] if it was rotated 4 times.
 * [0,1,4,4,5,6,7] if it was rotated 7 times.
 * <p>
 * <p>
 * Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results
 * in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
 * <p>
 * Given the sorted rotated array nums that may contain duplicates, return the
 * minimum element of this array.
 * <p>
 * You must decrease the overall operation steps as much as possible.
 * <p>
 * <p>
 * Example 1:
 * Input: nums = [1,3,5]
 * Output: 1
 * <p>
 * Example 2:
 * Input: nums = [2,2,2,0,1]
 * Output: 0
 * <p>
 * <p>
 * Constraints:
 * <p>
 * <p>
 * n == nums.length
 * 1 <= n <= 5000
 * -5000 <= nums[i] <= 5000
 * nums is sorted and rotated between 1 and n times.
 * <p>
 * <p>
 * <p>
 * Follow up: This problem is similar to Find Minimum in Rotated Sorted Array,
 * but nums may contain duplicates. Would this affect the runtime complexity? How and
 * why?
 * <p>
 * <p>
 * <p>
 * Related Topics 数组 二分查找 👍 555 👎 0
 */


package com.xixi.basicAlgroithms.binarySearch;

public class ID00154FindMinimumInRotatedSortedArrayIi {
    public static void main(String[] args) {
        Solution solution = new ID00154FindMinimumInRotatedSortedArrayIi().new Solution();
        solution.findMin(new int[]{1, 3, 5});
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findMin(int[] nums) {
            int n = nums.length;
            if (n == 1) return nums[0];


            int left = 0;
            int right = n - 1;
            //以right为坐标判断
            while (left < right) {//假设最小值在[0,n-2]区间内

                int mid = left + (right - left) / 2;


                if (nums[right] == nums[mid]) { //如果nums[mid] == nums[right]，right左移，这样不会丢失最小值。
                    right--;
                }

                if (nums[mid] < nums[right]) { //最小值在mid左边
                    right = mid;
                } else if (nums[mid] > nums[right]) {//最小值在mid右边
                    left = mid + 1;
                }
            }
            //最后假设n-1是最小值，说明nums[mid] > nums[right] 一直成立，left也会停止在n-1

            return nums[left];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}